package leetcode;

/**
 * 动态规划：一和零
 */
public class Solution47 {
    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            if(strs == null || strs.length == 0){
                return 0;
            }
            int[][] dp = new int[m + 1][n + 1];
            dp[0][0] = 0;
            //遍历数组
            for(String str: strs){
                int x = 0;
                int y = 0;
                for(char s : str.toCharArray()){
                    if(s == '0')
                        x++;
                    else
                        y++;
                }
                for(int i = m;i >= x;i--){
                    for(int j = n; j >= y;j--){
                        dp[i][j] = Math.max(dp[i][j],dp[i - x][j - y] + 1);
                    }
                }
            }
            return dp[m][n];
        }
    }
}
